//
// Created by Symps on 2025/11/16.
//

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left),
                                                       right(right) {}
};

using Node = TreeNode;

vector<vector<int>> zigzagLevelOrder(Node* root) {
    if (root == nullptr) {
        return {};
    }
    vector<vector<int>> ret;

    queue<Node*> q;
    q.push(root);
    int flag{};
    while (q.size()) {
        int sz(q.size());
        vector<int> leveri(sz);

        for (int i = 0; i < sz; ++i) {
            Node* curr{q.front()};
            q.pop();
            if (flag % 2) {
                leveri[sz - i - 1] = curr->val;
            } else {
                leveri[i] = curr->val;
            }

            if (curr->left) {
                q.push(curr->left);
            }
            if (curr->right) {
                q.push(curr->right);
            }
        }
        ret.push_back(leveri);
        ++flag;
    }
    return ret;
}

void test1() {
    Node* root{new Node(1)};
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = nullptr;
    root->right->left = nullptr;
    root->right->right = new Node(5);

    zigzagLevelOrder(root);
}

vector<int> largestValues(Node* root) {
    if (root == nullptr) {
        return {};
    }
    queue<Node*> q;
    q.push(root);
    vector<int> maxs;
    while (q.size()) {
        int sz(q.size());
        int m{};
        while (sz--) {
            Node* curr(q.front());
            q.pop();
            m = max(m, curr->val);

            if (curr->left) {
                q.push(curr->left);
            }
            if (curr->right) {
                q.push(curr->right);
            }

            // 5 3 2 7 6
        }
        maxs.push_back(m);
    }
    return maxs;
}

void test2() {
    Node* root = new Node(0);
    root->left = new Node(-1);
    auto ret = largestValues(root);
    for (auto& x : ret) {
        cout << x << " ";
    }
    cout << endl;
}

class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) : _k(k) {
        for (auto& x : nums) {
            add(x);
        }
    }

    int add(int val) {
        _heap.push(val);
        if (_k > _heap.size()) {
            _heap.pop();
        }
        return _heap.top();
    }

private:
    int _k;
    priority_queue<int, vector<int>, greater<int>> _heap;
};

class Solution {
public:
    class cmp {
    public:
        bool operator()(const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second == b.second) {
                return a.first > b.first;
            }
            return a.second < b.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> ret;
        map<string, int> m;
        for (string& str : words) {
            ++m[str];
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;
        for (auto&[str, times] : m) {
            heap.emplace(str, times);
        }
        while (k--) {
            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }

    // vector<string> topKFrequent(vector<string>& words, int k) {
    //     vector<string> ret;
    //     map<string, int, cmp> m;
    //
    //     for (string& str : words) {
    //         ++m[str];
    //     }
    //     for (auto&[str, times] : m) {
    //         ret.push_back(str);
    //     }
    //     return vector<string>(ret.begin(), ret.begin() + k);
    // }
};

void test3() {
    vector<string> words = {"apple", "banana", "apple", "orange", "banana", "banana"};
    Solution s;
    auto ret = s.topKFrequent(words, 2);
    for (auto& str : ret) {
        cout << str << " ";
    }
    cout << endl;
    // ret = s.topKFrequent(words, 2);
    // for (auto& str : ret) {
    //     cout << str << " ";
    // }
    // cout << endl;
}

class MedianFinder {
public:
    MedianFinder() {}

    void addNum(int num) {
        while (left_heap.size() < right_heap.size()) {
            left_heap.push(right_heap.top());
            right_heap.pop();
        }

        if (left_heap.size() == right_heap.size()) {
            left_heap.push(num);
        } else {
            right_heap.push(num);
        }
    }

    double findMedian() {
        if (left_heap.size() > right_heap.size()) {
            return left_heap.top();
        }
        return (left_heap.top() + right_heap.top()) * 1.0 / 2;
    }

private:
    priority_queue<int> left_heap;
    priority_queue<int, vector<int>, greater<int>> right_heap;
};

void test4() {
    MedianFinder mf;
    mf.addNum(1);
    mf.addNum(2);
    mf.addNum(3);
    cout << mf.findMedian() << endl;
}

int main() {
    // test1();
    // test2();
    // test3();
    test4();
    return 0;
}
